package leetcode_day._2023._11;

import java.util.Collections;
import java.util.List;

/**
 * 2824. 统计和小于目标的下标对数目
 * 算法: 排序 + 双指针或二分查找
 *
 * @author yezh
 * @date 2023/11/24 23:11
 */
public class _24 {

    public int countPairs_lowbound(List<Integer> nums, int target) {
        int ans = 0, n = nums.size();
        Collections.sort(nums);
        for (int i = 1; i < n; i++) {
            int l = 0, r = i - 1, tmp = target - nums.get(i);
            // nums[i] + nums[j] < target ==> nums[j] < target - nums[i]
            while (l <= r) {
                int mid = l + (r - l) / 2;
                if (nums.get(mid) < tmp) l = mid + 1;
                else r = mid - 1;
            }
            if (l - 1 > 0) ans += l - 1;
        }
        return ans;
    }

    public int countPairs(List<Integer> nums, int target) {
        int ans = 0, n = nums.size();
        Collections.sort(nums);
        for (int l = 0, r = n - 1; l < r; l++) {
            while (r >= 0 && nums.get(l) + nums.get(r) >= target) --r;
            if (l < r) ans += r - l;
        }
        return ans;
    }

}
